package com.c2b.algorithm.leetcode.jzoffer.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * <a href="https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/description/">从上到下打印二叉树 II</a>
 * <p>从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。</p>
 * <pre>
 *          3
 *         /  \
 *        9    20
 *            /  \
 *           15    7
 *  输入：{3,9,20,null,null,15,7}
 *  返回值：
 *      [
 *          [3],
 *          [9,20],
 *          [15,7]
 *      ]
 * </pre>
 *
 * @author c2b
 * @since 2023/3/9 13:44
 */
public class JzOffer0032LevelOrder_II {

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        // 队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 当前层最后一个节点
        TreeNode currLevelLastNode = root;
        // 下一层最后一个节点
        TreeNode nextLevelLastNode = null;
        TreeNode currentNode;
        List<Integer> currentLevelNodeValList = new ArrayList<>();
        while (!queue.isEmpty()) {
            currentNode = queue.poll();
            currentLevelNodeValList.add(currentNode.val);
            // 将左右子节点入队
            if (currentNode.left != null) {
                queue.offer(currentNode.left);
                nextLevelLastNode = currentNode.left;
            }
            if (currentNode.right != null) {
                queue.offer(currentNode.right);
                nextLevelLastNode = currentNode.right;
            }
            // 对本层数据节点进行汇总。进入到下一层
            if (currentNode == currLevelLastNode) {
                res.add(currentLevelNodeValList);
                currentLevelNodeValList = new ArrayList<>();
                currLevelLastNode = nextLevelLastNode;
                nextLevelLastNode = null;
            }
        }
        return res;
    }

    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        // 队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int currLevelNodeCount;
        TreeNode currNode;
        List<Integer> currentLevelNodeValList = new ArrayList<>();
        while (!queue.isEmpty()) {
            currLevelNodeCount = queue.size();
            for (int i = 0; i < currLevelNodeCount; i++) {
                currNode = queue.poll();
                currentLevelNodeValList.add(currNode.val);
                if (currNode.left != null) {
                    queue.offer(currNode.left);
                }
                if (currNode.right != null) {
                    queue.offer(currNode.right);
                }
            }
            res.add(currentLevelNodeValList);
            currentLevelNodeValList = new ArrayList<>();
        }
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(6);
        root.right = new TreeNode(10);
        root.right.left = new TreeNode(2);
        root.right.right = new TreeNode(1);
        JzOffer0032LevelOrder_II jzOffer0032PrintFromTopToBottom = new JzOffer0032LevelOrder_II();
        List<List<Integer>> lists = jzOffer0032PrintFromTopToBottom.levelOrder2(root);
        for (List<Integer> list : lists) {
            for (Integer integer : list) {
                System.out.print(integer + "  ");
            }
            System.out.println();
        }
    }
}
